package hot100.logos91To100;

/**
 * @author logos
 * date 2025/7/19 12:50
 * @version v1.0
 * @Package hot100.logos91To100
 */
public class logos95 {

    /**
     * 95. 编辑距离
     * https://leetcode.cn/problems/edit-distance/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int minDistance(String word1, String word2) {
            return editDistance(word1, word2, 1, 1, 1);
        }

        public static int editDistance(String str1, String str2, int a, int b, int c) {
            char[] s1 = str1.toCharArray();
            char[] s2 = str2.toCharArray();
            int n = s1.length;
            int m = s2.length;
            int[] dp = new int[m + 1];
            for (int j = 1; j <= m; j++) {
                dp[j] = j * a;
            }
            for (int i = 1, leftUp, backUp; i <= n; i++) {
                leftUp = (i - 1) * b;
                dp[0] = i * b;
                for (int j = 1; j <= m; j++) {
                    backUp = dp[j];
                    if (s1[i - 1] == s2[j - 1]) {
                        dp[j] = leftUp;
                    } else {
                        dp[j] = Math.min(Math.min(dp[j] + b, dp[j - 1] + a), leftUp + c);
                    }
                    leftUp = backUp;
                }
            }
            return dp[m];
        }
    }
}
